#include <bits/stdc++.h>

using namespace std;


const int N=1000;
int dp[N][N],n,m,k;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j)dp[i][j]=0;
			else dp[i][j]=0x3f3f3f3f;
		}
	}
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		dp[a][b]=min(dp[a][b],c);
	}
	for(int o=1;o<=n;o++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dp[i][j]=min(dp[i][j],dp[i][o]+dp[o][j]);
			}
		}
	}
	while(k--){
		int a,b;
		cin>>a>>b;
		if(dp[a][b]==0x3f3f3f3f/2)puts("impossible");
		else cout<<dp[a][b]<<endl;
	}
}
